Orthogononalization on a general purpose graphics processing unit with double double and quad double arithmetic

摘要

Our problem is to accurately solve linear systems on a general purposegraphics processing unit with double double and quad double arithmetic. Thelinear systems originate from the application of Newton's method on polynomialsystems. Newton's method is applied as a corrector in a path following method,so the linear systems are solved in sequence and not simultaneously. Onesolution path may require the solution of thousands of linear systems. Inprevious work we reported good speedups with our implementation to evaluate anddifferentiate polynomial systems on the NVIDIA Tesla C2050. Although the costof evaluation and differentiation often dominates the cost of linear systemsolving in Newton's method, because of the limited bandwidth of thecommunication between CPU and GPU, we cannot afford to send the linear systemto the CPU for solving during path tracking. Because of large degrees, the Jacobian matrix may contain extreme values,requiring extended precision, leading to a significant overhead. This overheadof multiprecision arithmetic is our main motivation to develop a massivelyparallel algorithm. To allow overdetermined linear systems we solve linearsystems in the least squares sense, computing the QR decomposition of thematrix by the modified Gram-Schmidt algorithm. We describe our implementationof the modified Gram-Schmidt orthogonalization method for the NVIDIA TeslaC2050, using double double and quad double arithmetic. Our experimental resultsshow that the achieved speedups are sufficiently high to compensate for theoverhead of one extra level of precision.